#pragma once
#include<iostream>
#include<stack>
#include"Graph_Functions.h"
using namespace std;

class tarjaning{
public:
	int size;
	vector<int>Time_In;
	vector<int>Lowest_Time;
	int cur_time;
	stack<int> vertex_stack;
	int cur_component;
	vector<int>components;
	void initialize(const unique_ptr<IGraph> & graph, int start)
	{
		size = graph->get_number_of_vertice();
		Time_In.resize(size); 
		Lowest_Time.resize(size);
		cur_time = 0;
		cur_component = 0;
		components.assign(size, -1);
	//	 FIRST_TYPE_OPERATION = 1;
	//	SECOND_TYPE_OPERATION = 4;
	//	 FIRST_TYPE_EDGE_OPERATION = 2;
	//	SECOND_TYPE_EDGE_OPERATION = 3;
	}

	void  enter_vertex (const unique_ptr<IGraph> & graph, int vertex, vector<int>& color)
	{
		cur_time++; //cerr << "kagdila? \n";
		//cerr << "vertex: " << vertex << "\n";
		Time_In[vertex] = cur_time; 
		color[vertex] = 1;
		vertex_stack.push(vertex);
		Lowest_Time[vertex] = cur_time;
	}

	void exit_vertex (const unique_ptr<IGraph> & graph, int vertex, vector<int>& color)
	{
		if (Lowest_Time[vertex] == Time_In[vertex])
		{
			cur_component++;
			while (true)
			{
				int cur_vertex = vertex_stack.top();
				vertex_stack.pop();
				components[cur_vertex] = cur_component;
				//cerr << " components for " << cur_vertex << " is " << cur_component << "\n";
				if (cur_vertex == vertex) break; 
			}
		}
	}

	void after_edge (const unique_ptr<IGraph> & graph, int vertex, int to, vector<int>& color)
	{
		if (!(color[to] == 2 && components[to] != -1))Lowest_Time[vertex] = min(Lowest_Time[vertex], Lowest_Time[to]);
	}

	void before_edge (const unique_ptr<IGraph> & graph, int vertex, int to, vector<int>& color)
	{
		
	}

	void final(const unique_ptr<IGraph> & graph)
	{
		int maximal = 0;
		for (int vertex = 0; vertex < size; ++vertex)if (maximal < components[vertex]) maximal = components[vertex];
		for (int vertex = 0; vertex < size; ++vertex)components[vertex] = maximal - components[vertex];
	}
};

vector<int> component(unique_ptr<IGraph>& graph)
{
	tarjaning cluster;
	commondfs<tarjaning> clustered(graph, -1, cluster);
	clustered.dfscycle(graph, cluster);
	return cluster.components;
}
